#include <bits/stdc++.h>

using namespace std;

// 打家劫舍 IV
// 沿街有一排连续的房屋。每间房屋内都藏有一定的现金
// 现在有一位小偷计划从这些房屋中窃取现金
// 由于相邻的房屋装有相互连通的防盗系统，所以小偷不会窃取相邻的房屋
// 小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额
// 给你一个整数数组 nums 表示每间房屋存放的现金金额
// 第i间房屋中放有nums[i]的钱数
// 另给你一个整数k，表示小偷需要窃取至少 k 间房屋
// 返回小偷需要的最小窃取能力值
// 测试链接 : https://leetcode.cn/problems/house-robber-iv/

class Solution 
{
public:
    int minCapability(vector<int>& nums, int k) 
    {
        // int l = *min_element(nums.begin(), nums.end());
        // int r = *max_element(nums.begin(), nums.end()); // 返回最大元素迭代器的位置
        int l = nums[0], r = nums[0];
        for(int i = 1; i < nums.size(); ++i)
        {
            l = min(l, nums[i]);
            r = max(r, nums[i]);
        }

        int ans = 0;
        while(l <= r)
        {
            int m = l + ((r - l) >> 1);
            if(mostRob3(nums, m) >= k)
            {
                ans = m;
                r = m - 1;
            }
            else l = m + 1;
        }   
        return ans;
    }

	// 盗贼能力为ability时
	// 返回盗贼最多能窃取多少间房屋
	// 注意限制 : 不能窃取相邻房屋
    int mostRob1(vector<int>& nums, int ability)
    {
        int n = nums.size();
        if(n == 1) return nums[0] <= ability ? 1 : 0;
        if(n == 2) return min(nums[0], nums[1]) <= ability ? 1 : 0;

        int dp[n];
        dp[0] = nums[0] <= ability ? 1 : 0;
        dp[1] = min(nums[0], nums[1]) <= ability ? 1 : 0;
        for(int i = 2; i < n; ++i)
        {
            dp[i] = max(dp[i - 1], dp[i - 2] + (nums[i] <= ability ? 1 : 0));
        }
        return dp[n - 1];
    }

    // 继续空间压缩优化
    int mostRob2(vector<int>& nums, int ability)
    {
        int n = nums.size();
        if(n == 1) return nums[0] <= ability ? 1 : 0;
        if(n == 2) return min(nums[0], nums[1]) <= ability ? 1 : 0;

        int lastLast = nums[0] <= ability ? 1 : 0;
        int last = min(nums[0], nums[1]) <= ability ? 1 : 0;
        for(int i = 2, cur; i < n; ++i)
        {
            cur = max(last, lastLast + (nums[i] <= ability ? 1 : 0));
            lastLast = last;
            last = cur;
        }
        return last;
    }

    // 继续贪心优化
    int mostRob3(vector<int>& nums, int ability)
    {
        int ans = 0;
        for(int i = 0; i < nums.size(); ++i)
        {
            if(nums[i] <= ability)
            {
                ++ans;
                ++i;
            }
        }
        return ans; 
    }
};